Merge overlapping intervals

Time: O(NlogN); Space: O(1); hard

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: intervals: [1, 3], [2, 6], [8, 10], [15, 18]

Output: [1, 6], [8, 10], [15, 18]

[14]:

class Interval:
    def __init__(self, start = 0, end = 0):
        self.start = start
        self.end = end

    def __repr__(self):
        return "[{}, {}]".format(self.start, self.end)

class Solution1(object):
    def merge(self, intervals) -> list:
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        if not intervals:
            return intervals

        intervals.sort(key=lambda x: x.start)

        result = [intervals[0]]

        for i in range(1, len(intervals)):
            prev, current = result[-1], intervals[i]
            if current.start <= prev.end:
                prev.end = max(prev.end, current.end)
            else:
                result.append(current)

        return result

[15]:

s = Solution1()
list_of_intervals = s.merge([Interval(1, 3), Interval(2, 6), Interval(8, 10), Interval(15,18)])
res = []
for ivl in list_of_intervals:
    res.append([ivl.start, ivl.end])
assert res == [[1, 6], [8, 10], [15, 18]]